package com.problem.leetcode;

import com.google.common.base.Stopwatch;

/**
 * @author yanzhuoleo
 * @version V1.0
 * @Description: 求出若干个字符串的最长公共前缀
 * @date 2018-01-03-下午4:52
 */

public class Problem14 {
    public static void main(String[] args) {
        Stopwatch stopwatch = Stopwatch.createStarted();
        System.out.println(longestCommonPrefix(new String[]{
                "abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabc",
                "abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabc"}));
        stopwatch.stop();
        System.out.println(stopwatch.toString());
    }

    public static String longestCommonPrefix(String[] strs) {
        StringBuilder builder = new StringBuilder("");
        int           j       = 0;

        if (strs.length == 1) {
            return strs[0];
        }

        if (strs.length == 0) {
            return "";
        }

        for (int index = 0; index < strs.length; ++index) {

            if (builder.length() >= strs[index].length()) {
                //说明已经找到了最大前缀
                break;
            }

            char element = strs[0].charAt(j);

            if (element != strs[index].charAt(j)) {
                // 除了第一个字符串外 其他的字符串不包含特定字符 所以退出
                break;
            }

            if (index == strs.length - 1) {
                builder.append(strs[index].charAt(j));
                ++j;
                index = -1;

            }
        }

        return builder.toString();
    }

}
